package com.mj.listen2._01_排序.cmp;

/**
 * 插入排序的优化，借用二分搜索的思想
 *
 * @param <T>
 */
public class _05_InsertSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            insert(i, search(i));
        }
    }

    /**
     * 将source位置的元素插入到dest位置
     */
    private void insert(int source, int dest) {
        T value = array[source];
        // 数组的元素依次往后顺移
        for (int i = source; i > dest; i--) {
            // 将前面的元素依次往后顺移
            array[i] = array[i - 1];
        }
        array[dest] = value;
    }

    /**
     * 去有序数组中，查找出现第一次比 index 位置元素大的索引
     *
     * @param index
     */
    private int search(int index) {
        T value = array[index];
        int begin = 0;
        int end = index;
        int mid;
        while (begin < end) {
            mid = (begin + end) >> 1;
            if (cmp(value, array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}
